/**
 * 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * <p>
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 * <p>
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *  
 * <p>
 * 提示：
 * <p>
 * 每个字符串仅由字符 '0' 或 '1' 组成。
 * 1 <= a.length, b.length <= 10^4
 * 字符串如果不是 "0" ，就都不含前导零。
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(addBinary("11", "1"));
    }

    /**
     * 用的反转之后处理，如果不反转处理可能会更加快，比如直接倒序对两个字符串进行遍历
     *
     * @param a
     * @param b
     * @return
     */
    public static String addBinary(String a, String b) {
        a = new StringBuilder(a).reverse().toString();
        b = new StringBuilder(b).reverse().toString();
        StringBuilder sb = new StringBuilder();
        int i = 0, tmp = 0;
        while (i < a.length() || i < b.length()) {
            if (i < a.length()) {
                tmp += a.charAt(i) - '0';
            }
            if (i < b.length()) {
                tmp += b.charAt(i) - '0';
            }
            if (tmp == 0) {
                sb.append("0");
            } else if (tmp == 1) {
                sb.append("1");
                tmp = 0;
            } else if (tmp == 2) {
                sb.append("0");
                tmp = 1;
            } else if (tmp == 3) {
                sb.append("1");
                tmp = 1;
            }
            i++;
        }
        if (tmp == 1) {
            sb.append("1");
        }
        return sb.reverse().toString();
    }
}